package com.jxb.dp20251355;

/**
 * 类注释
 *
 * @author jiaobo
 * @date Created in 2025/1/6 20:35
 **/
public class LongestPalindromic_DP_5 {

    //dp[i][j]代表开始位置和结束位置所构成的子串是否时回文串
    //当i和j相等时，必为回文字串
    //并且j>i的
    //状态转移公式：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
    public String longestPalindrome(String s) {
        //处理原始字符只有1个或者2个
        int len = s.length();
        if (len == 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        if (len == 2) {
            if (chars[1] == chars[0]) {
                return s;
            }else {
                return s.substring(0,1);
            }
        }

        //定义回文字串的开始索引和最大长度索引
        int begin = 0;
        int maxlen = 1;

        //定义dp数组
        boolean[][] dp = new boolean[len][len];
        //初始化dp数组
        for (int i = 0;i<len;i++) {
            dp[i][i] = true;
        }
        //填充dp数组，j比i大
        for (int j = 1;j<len;j++) {
            for (int i = 0;i<j;i++) {
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                }else {
                    //i和j索引处元素相等
                    //j-i<3:说明i和j中间只有1个元素
                    if (j-i < 3) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //若当前时回文字串，并且，回文字串的长度大于之前的长度，堆索引进行重新赋值
                if (dp[i][j] && j - i + 1 > maxlen) {
                    maxlen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+maxlen);
    }

}
